package org.lep.leetcode.besttimetobuyandsellstock;

/**
 * Source : https://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock/
 *
 * Created by lverpeng on 2017/8/19.
 *
 * Say you have an array for which the ith element is the price of a given stock on day i.
 *
 * If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock),
 * design an algorithm to find the maximum profit.
 */
public class BestTimeToBuyAndSellStock {

    /**
     * 给定一段时间范围内股票的价格判断什么时候买进和卖出所得的利润最大，最大是多少
     *
     * 只需要找出最低价格和最高价就可以，但是要注意，买进肯定是在卖出之前，所以最小值要在最大值前面
     *
     * 遍历数组，找出i之前的最小值，将当前元素prices[i]与minimum比较
     * prices[i] < minimum 更新minimum，minimum = prices[i]
     * prices[i] >= minimum 计算当前的最大值利润
     *
     *
     * @param prices
     * @return
     */
    public int maxProfit (int[] prices) {
        if (prices.length <= 1) {
            return 0;
        }
        int min = prices[0];
        int maxProfit = Integer.MIN_VALUE;
        for (int i = 1; i < prices.length; i ++) {
            if (prices[i] < min) {
                min = prices[i];
            } else {
                int profit = prices[i] - min;
                maxProfit = profit > maxProfit ? profit : maxProfit;
            }
        }
        return maxProfit;
    }

    public static void main(String[] args) {
        BestTimeToBuyAndSellStock bestTimeToBuyAndSellStock = new BestTimeToBuyAndSellStock();
        System.out.println(bestTimeToBuyAndSellStock.maxProfit(new int[]{1,2,3,4,5}));
        System.out.println(bestTimeToBuyAndSellStock.maxProfit(new int[]{1,-2,3,5,-9}));
    }
}
